package com.cuz.daileetcode;

import java.util.Arrays;

public class Day23 {

    /****
     * 归并排序（Merging Sort）就是利用归并的思想实现的排序方法。
     * 他的原理是
     * 假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，
     * 然后两两归并，得到n/2 （取上界） 个长度为2或1的有序子序列；
     * 再两两归并…，如此重复，直至得到一个长度为n的有序的序列为止，这种排序称为2路归并排序。
     */
    static class MergeSort {
        public static void main(String[] args) {
            int[] ints = {2, 1, 3, 5, 7, 6};
            mergeSort(ints);
            System.out.println(Arrays.toString(ints));
        }

        static void mergeSort(int[] arr) {
            //空数组 和元素小于2个都结束 0个元素不需要排序，1个元素也不需要排序
            if (arr == null || arr.length < 2) {
                return;
            }
            recursion(arr, 0, arr.length - 1);
        }

        static void recursion(int[] arr, int left, int right) {

            if (left < right) {
                int mid = left + ((right - left) >> 1);
                //排序左边，在排序右边，两边有序后合并左右
                recursion(arr, left, mid);
                recursion(arr, mid + 1, right);
                merge(arr, left, mid, right);
            }
        }

        static void merge(int[] arr, int left, int mid, int right) {
            int count = 0;
            int leftIndex = left;
            int rightIndex = mid + 1;
            int[] tempArray = new int[right - left + 1];
            while (leftIndex <= mid && rightIndex <= right) {
                if (arr[leftIndex] < arr[rightIndex]) {
                    tempArray[count] = arr[leftIndex];
                    leftIndex++;
                } else {
                    tempArray[count] = arr[rightIndex];
                    rightIndex++;
                }
                count++;
            }
            //左边有剩余
            while (leftIndex <= mid) {
                tempArray[count] = arr[leftIndex];
                leftIndex++;
                count++;
            }
            while (rightIndex <= right) {
                tempArray[count] = arr[rightIndex];
                rightIndex++;
                count++;
            }
            for (int index = 0; index < tempArray.length; index++) {
                arr[left + index] = tempArray[index];
            }
        }
    }

    /***
     * 在一个数组中， 每一个数左边比当前数小的数累加起来， 叫做这个数组的小和。 求一个数组的小和。
     * 例子：[1,3,4,2,5]
     * 1左边比1小的数， 没有；
     * 3左边比3小的数，1；
     * 4左边比4小的数，1、3；
     * 2左边比2小的数，1；
     * 5左边比5小的数，1、3、4、2；
     * 所以小和为1+1+3+1+1+3+4+2=16
     *
     * 使用归并排序来进行求和，在归并的时候把数组分成左右两个，
     * 在归并排序进行左右两个数组进行合并排序的时候进行计算。
     * 如果左边数组元素N，小于右边数组元素M，那么从右边数组右指针P到右边数组最后R就有(R-P+1)个N，
     * 依次累计相加，最后求出最小和。
     */
    static class SmallSum {
        //总体思路和归并排序一致，在合并的过程中计算小和
        public static int smallSum(int[] arr) {
            if (arr == null || arr.length < 2) {
                return 0;
            }
            return mergeSort(arr, 0, arr.length - 1);
        }

        public static int mergeSort(int[] arr, int l, int r) {
            if (l == r) {
                return 0;
            }
            int mid = l + ((r - l) >> 2);
            return mergeSort(arr, l, mid)
                    + mergeSort(arr, mid + 1, r)
                    + merge(arr, l, mid, r);
        }

        public static int merge(int[] arr, int l, int m, int r) {
            int[] help = new int[r - l + 1];
            int i = 0;
            int p1 = l;
            int p2 = m + 1;
            int res = 0;
            while (p1 <= m && p2 <= r) {
                //在合并的过程中计算小和
                res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
                help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
            }
            while (p1 <= m) {
                help[i++] = arr[p1++];
            }
            while (p2 <= r) {
                help[i++] = arr[p2++];
            }
            for (i = 0; i < help.length; i++) {
                arr[l + i] = help[i];
            }
            return res;
        }
    }

    /***
     * 使用归并排序来进行求和，在归并的时候把数组分成左右两个，
     * 在归并排序进行左右两个数组进行合并排序的时候进行计算。
     * 如果左边数组元素N，小于右边数组元素M，那么从右边数组右指针P到右边数组最后R就有(R-P+1)个N，
     * 依次累计相加，最后求出最小和。
     *
     * 使用归并排序来进行求和，在归并的时候把数组分成左右两个，
     * 在归并排序进行左右两个数组进行合并排序的时候进行计算。
     * 如果左边数组元素N，小于右边数组元素M，那么从右边数组右指针P到右边数组最后R就有(R-P+1)个N，
     * 依次累计相加，最后求出最小和。
     */
    static class ReverseOrder {
        public static void reverseOrder(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            mergeSort(arr, 0, arr.length - 1);
        }

        public static int mergeSort(int[] arr, int l, int r) {
            if (l == r) {
                return 0;
            }
            int mid = (l + r) / 2;
            int k = mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
            System.out.println("merge总逆序数：" + k);
            return k;
        }

        public static int merge(int[] arr, int l, int mid, int r) {
            int mergeRes = 0;
            int[] help = new int[r - l + 1];   //help的长度不是一个大的N 而是每次分治 的长度
            int i = 0;
            int p1 = l;
            int p2 = mid + 1;

            while (p1 <= mid && p2 <= r) {
                if (arr[p2] < arr[p1]) {    //说明p2此时比p1中剩下的元素都小
                    mergeRes += (mid - p1 + 1);  //核心
                    ////打印此时的逆序对
                    for (int k = 0; k < mid - p1 + 1; k++) {
                        System.out.println(arr[p1 + k] + " " + arr[p2]);
                    }
                }
                help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
            }
            while (p1 <= mid) {
                help[i++] = arr[p1++];
            }
            while (p2 <= r) {
                help[i++] = arr[p2++];
            }
            //拷贝到 arr数组
            for (int j = 0; j < help.length; j++) {
                arr[l + j] = help[j];
            }
            System.out.println("mergeRes:" + mergeRes);
            return mergeRes;
        }
    }
}
